﻿#pragma once
#include "stdafx.h"

/*
最长回文子串  中等
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

解题想法，汇文串是对称性质，找到中心位置然后，依次判断左右是否为对称，时间复杂度O(N^2)

目前最优解法：
Manacher 算法，被中国程序员戏称为“马拉车”算法。它专门用于解决“最长回文子串”问题，时间复杂度为 O(N)。

*/

string centerSpread(string s, int left, int right) {
	// left = right 的时候，此时回文中心是一个空隙，向两边扩散得到的回文子串的长度是奇数
	// right = left + 1 的时候，此时回文中心是一个字符，向两边扩散得到的回文子串的长度是偶数
	int size = s.size();
	int i = left;
	int j = right;
	while (i >= 0 && j < size) {
		if (s[i] == s[j]) {
			i--;
			j++;
		}
		else {
			break;
		}
	}
	// 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
	return s.substr(i + 1, j - i - 1);
}


string longestPalindrome(string s) 
{
	// 特判
	int size = s.size();
	if (size < 2) {
		return s;
	}

	int maxLen = 1;
	string res = s.substr(0, 1);

	// 中心位置枚举到 len - 2 即可
	for (int i = 0; i < size - 1; i++) {
		string oddStr = centerSpread(s, i, i);
		string evenStr = centerSpread(s, i, i + 1);
		string maxLenStr = oddStr.size() > evenStr.size() ? oddStr : evenStr;
		if (maxLenStr.length() > maxLen) {
			maxLen = maxLenStr.size();
			res = maxLenStr;
		}
	}
	return res;
}
